package com.lcm.learn.lcmcode.sort;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @description:
 * @author: lcm
 * @create: 2020-01-20 15:52
 **/

public class QuickSort implements Sort{
    public int i=0;

    public static void main(String[] args){
        QuickSort quickSort=new QuickSort();
        int len=1000000;
        int[] array=new int[len];
        for(int i=0;i<len;i++){
            array[i] = (int)(Math.random()*10000);
        }
        int[] copyArray = Arrays.copyOf(array, array.length);
        Arrays.sort(copyArray);
        array=copyArray;
        //System.out.println("排序前："+Arrays.toString(array));
        long startTime = System.currentTimeMillis();
        try {
            //quickSort.quickSort(array,0,array.length-1);
            quickSort.sort(array);
        }catch (StackOverflowError e){
            e.printStackTrace();
        }finally {
            System.out.println(quickSort.i);
        }

        System.out.println("排序时间/ms："+(System.currentTimeMillis()-startTime));
        //System.out.println("排序后："+Arrays.toString(array));
        System.out.println("是否正确："+Arrays.equals(array,copyArray));
    }


    @Override
    public void sort(int[] array) {
        //sort(array,0,array.length-1);
        quickSort(array,0,array.length-1);
    }

    public void sort(int[] array,int from,int to) {
        int base=array[from];
        int index=from;
        int next=to;
        for(int i=from;i<to;i++){
            if(index<next){
                if(array[next]<=base){
                    array[index]=array[next];
                    int temp=index;
                    index=next;
                    next=temp+1;
                }else{
                    next--;
                }
            }else{
                if(array[next]>=base){
                    array[index]=array[next];
                    int temp=index;
                    index=next;
                    next=temp-1;
                }else{
                    next++;
                }
            }
        }
        array[index]=base;
        if(from<index-1){
            sort(array,from,index-1);
        }
        if(index+1<to){
            sort(array,index+1,to);
        }
    }

    public void sortIter(int[] array) {
        LinkedList<Integer> list=new LinkedList<>();
    }

//    public void sortIterHelp(int[] array, LinkedList<Integer> list) {
//        int len=list.size();
//        for(int j=0;j<len;j=+2){
//            int base=array[list.getFirst()];
//            int index=list.getFirst();
//            int next=to;
//            for(int i=from;i<to;i++){
//                if(index<next){
//                    if(array[next]<=base){
//                        array[index]=array[next];
//                        int temp=index;
//                        index=next;
//                        next=temp+1;
//                    }else{
//                        next--;
//                    }
//                }else{
//                    if(array[next]>=base){
//                        array[index]=array[next];
//                        int temp=index;
//                        index=next;
//                        next=temp-1;
//                    }else{
//                        next++;
//                    }
//                }
//            }
//            array[index]=base;
//        }
//
//
//    }

    public static void quickSort(int a[], int low, int high) {  // 这里其实 low = 0；high = r.length-1; 但是后面要用递归，需要指定不同的边界
        int i, j, temp;   //temp 用于保存基准元素
        if(low < high) {   // 这里确保待比较的元素个数大于 1
            i = low;
            j = high;
            temp = a[i];  // 令第一个数据为基准
            while(i<j) {
                while(i<j && a[j]>=temp) j--; // 从数组的右端向左依次和基准比较，直到遇到小于基准的数或者比较完依然没遇到。
                // 注意，相等的时候也要换过去，这也造成快排不具有稳定性
                if(i<j){    // 如果在没比较完之前遇到，则：
                    a[i] = a[j]; i++;  // 右侧较小的数挪到数组左侧去，注意这里不用交换，因为基准数已经保存在变量 temp 里了
                }
                while(i<j&&a[i]<=temp) i++; // 然后又从左侧向右开始和基准比较
                if(i<j){a[j] = a[i]; j--;   // 直到遇到大于基准的数，将其挪到数组右侧去
                }
            }
            a[i] = temp; // 直到 i 和 j 相遇时第一圈比完，这个位置就应该是基准在数组排序中的位置，且此时 i=j
            if(low < i-1) quickSort(a,low,i-1); // 最后对基准左侧和右侧的数据不断重复上述过程
            if(high > j+1) quickSort(a,j+1,high); // 注意 if 里的判断条件, 因为此时 r[i] or r[j] 已经不需要再比较
        }

    }
}
